递归和动态规划——最长递增子序列

Posted on | In ,

题目：给定数组arr=[2,1,5,3,6,4,8,9,7]，返回最长递增子序列，即[1,3,4,8,9]。
要求：若arr长度为N，时间复杂度为O(NlogN)。

实现
方法一：时间复杂度为O(N^2)
步骤一：生成长度为N的数组dp，dp[i]表示以arr[i]这个数结尾的情况下，arr[0,…i]中的最大递增子序列长度。

  1. 对于第一个数dp[0]=1，接下来一次算出每个位置的数结尾的情况下的最大递增子序列长度。
  2. 对于dp[i]，它以arr[i]结尾，arr[0,…i-1]中比arr[i]小的数都可以作为arr[i]的倒数第二个节点，选择以那个数（如arr[j]）结尾的最大递增子序列（如dp[j]）最大的那个数作为倒数第二个数，即dp[i] = max{dp[j]+1}，0<=j<i,arr[j]<arr[i]（由于说了是递增，不是非减，所以arr[j]与arr[i]之间没有等号）。
  3. 若arr[0,…i-1]中，没有比arr[i]小的数，则令dp[i]=1，即其最大递增子序列就是自身。

结果为dp=[1,1,2,2,3,3,4,5,4]。

步骤二：根据dp数组得到最长递增子序列

  1. 遍历dp数组，找到最大值（即最长递增子序列的长度）及位置。本例中最大值为5，位置为7。
  2. 从arr[7]开始从右向左遍历。如果对于某一位置i，有arr[i]<arr[7] && dp[i]=dp[7]-1，则arr[i]可作为最长递增子序列的倒数第二个数，本例中为arr[6]=8。
  3. 然后继续从位置6向左遍历，直到所有数据都找出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.concurrent.SynchronousQueue;
/*
 * 求最长递增子序列，总的时间复杂度为O(N^2)
 */
public class Getdp {	
	/**
	 * 1. 求出记录以每个数结尾的最长递增子序列的长度
	 * 时间复杂度为O(N^2)
	 * @param arr 原数组
	 * @return 记录最长递增子序列个数的数组
	 */
	public static int[] getdp1(int[] arr){
		int[] dp = new int[arr.length];
		for (int i = 0; i < arr.length; i++){ //遍历arr数组中的数
			dp[i] = 1;  //初始状态，每个数都以自己为最长递增子序列
			//只要j<i且arr[i]>arr[j]就从0开始比较，更新dp[i]
			for (int j = 0; j < i; j++){ 
				if(arr[i] > arr[j]){
					dp[i] = Math.max(dp[j] + 1, dp[i]); 
				}
			}
		}
		return dp; //返回数组，返回数组名就可以了
	}
	/**
	 * 2. 找到dp数组中数值最大的数及其对应的arr[i],
	 * 并打印以这个数结尾的最长递增子序列，时间复杂度为O(N)
	 * @param arr 原数组
	 * @param dp 记录以arr[i]结尾的最长递增子序列的长度
	 * @return 最长递增子序列
	 */
	public static int[] generateList(int[] arr, int[] dp) {
		int len = 0; 
		int index = 0; 
		//找到一个dp数组中数值最大的数len及其下标index
		for (int i = 0; i < dp.length; i++) {
			if (dp[i] > len) {
				len = dp[i];
				index = i;
			}
		}
		int[] list = new int[len] ; //存arr中的最长递增子序列,若len=5
		list[--len] = arr[index]; //这里的先减1是考虑到数组长度与索引的对应问题
		//从arr[index]开始从右向左遍历arr
		for (int i = index; i >= 0; i--) {
			if (arr[i] < arr[index] && dp[i] == dp[index] -1) {
				list[--len] = arr[i]; ///这里的先减1是考虑到数组长度与索引的对应问题
				index = i; //这一步注意，使循环变得高效，跳过arr中不满足的值
			}
		}
		return list;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
	//Test
	public static void main(String[] args) {
		int[] arr = {2,1,5,3,6,4,8,9,7};
		int[] dp = getdp1(arr);
		System.out.println("dp[i]保存的是以arr[i]结尾的最长递增子序列的长度：");
		for (int i : dp) { 
			System.out.print(i + " ");
		}
		int[] laList = generateList(arr, dp);
		System.out.println();
		System.out.println("最长递增子序列为：");
		for (int i : laList) { 
			System.out.print(i + " ");
		}
	}
}

输出：

dp[i]保存的是以arr[i]结尾的最长递增子序列的长度：
1 1 2 2 3 3 4 5 4 
最长递增子序列为：
1 3 4 8 9

方法二：利用二分查找对生成dp数组的过程进行优化，时间复杂度为O(NlogN)